home *** CD-ROM | disk | FTP | other *** search
/ PD ROM 1 / PD ROM Volume I - Macintosh Software from BMUG (1988).iso / Stacks / Updates⁄New / TEXAS for BMUG / C progs / qndxr.2 ƒ / merge_indices.2.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-11-03  |  3.7 KB  |  115 lines  |  [TEXT/KAHL]
  1. /* file "merge_indices.c" ... by ^z -- 870823-...
  2.  * function to merge sorted indices together repeatedly until finished
  3.  * with them all in a single set of *.k/*.p files ...
  4.  *
  5.  * The merging strategy is straightforward enough:
  6.  *    Let "g" denote the generation_number and "f" denote the file_number.
  7.  *    Temporary file names begin with the letter x, which is then followed
  8.  *    by a generation number (decimal), the letter k or p (standing for
  9.  *    key or ptr, respectively), and then the file number (decimal).  Thus,
  10.  *    the file "x0k0" is the keys file #0 for generation #0 (the starting,
  11.  *    pre-merging, generation), file "x2p3" is the ptr file #3 for generation
  12.  *    #2, etc.
  13.  *
  14.  * (The following discussion is specifically for a 2-way merge ... but
  15.  * the generalization for N-way merging is straightforward.)
  16.  *
  17.  *    On a given call to merge_indices, the following may happen:
  18.  *        - files xgkf/xgpf and xgk(f+1)/xgp(f+1) are merged into files
  19.  *            x(g+1)k(f/2)/x(g+1)p(f/2), and then the parent files are
  20.  *            deleted;
  21.  *        - file xgkf isn't found, which means we are done with this
  22.  *            generation and must go on to the next;
  23.  *        - file xgk(f+1) isn't found, which means that either we are
  24.  *            completely done with the merging work (if f=0) and just
  25.  *            have to rename the files xgkf/xgpf into the correct final
  26.  *            names (that is, doc_filename.k/doc_filename.p), or else
  27.  *            (if f>0) we have an odd number of files for this level
  28.  *            of merging, and therefore just have to rename xgkf/xgpf
  29.  *            to x(g+1)k(f/2)/x(g+1)p(f/2).
  30.  */
  31.  
  32.  
  33. #include <stdio.h>
  34. #include <unix.h>
  35. #include <storage.h>
  36. #include <strings.h>
  37. #include <ctype.h>
  38. #include <proto.h>
  39. #include "qndxr.2.h"
  40.  
  41. int merge_indices (doc_filename)
  42.   char *doc_filename;
  43.   {
  44.     static int generation_number = 0, file_number = 0;
  45.     FILE *ink[NMERGE], *inp[NMERGE], *outk, *outp, *open_inkfile(),
  46.             *open_inpfile(), *open_outkfile(), *open_outpfile();
  47.     void fix_oddball_file_name(), fix_final_file_names(), merge_kpfiles(),
  48.             remove_used_infiles(), close_infiles();
  49.     long inwords, indistinctwords, outdistinctwords, file_size();
  50.     int i, n;
  51.     
  52.     for (n = 0; n < NMERGE; ++n)
  53.       {
  54.         ink[n] = open_inkfile (generation_number, file_number + n);
  55.         if (ink[n] == NULL)
  56.             break;
  57.         inp[n] = open_inpfile (generation_number, file_number + n);
  58.       }
  59.     
  60.     if (file_number + n == 1)
  61.       {
  62.         DEBUG ("--All finished with merging files!\n", NULL);
  63.         printf ("\nFinished with index sorting!  Final file sizes:\n");
  64.         printf ("%9ld bytes of distinct key words\n", file_size (ink[0]));
  65.         printf ("%9ld bytes of pointers to words\n", file_size (inp[0]));
  66.         close_infiles (ink, inp, n);
  67.         fix_final_file_names (generation_number, doc_filename);
  68.         return (FALSE);
  69.       }
  70.     
  71.     if (n < 2)
  72.       {
  73.         DEBUG ("--finished generation_number=%d ", generation_number);
  74.         DEBUG ("-- file_number=%d\n", file_number);
  75.         if (n == 1)
  76.           {
  77.             close_infiles (ink, inp, n);
  78.             fix_oddball_file_name (generation_number, file_number);
  79.           }
  80.         ++generation_number;
  81.         file_number = 0;
  82.         return (TRUE);
  83.       }
  84.     
  85.     outk = open_outkfile (generation_number, file_number);
  86.     outp = open_outpfile (generation_number, file_number);
  87.     
  88.     inwords = 0;
  89.     indistinctwords = 0;
  90.     for (i = 0; i < n; ++i)
  91.       {
  92.         inwords += file_size (inp[i]) / sizeof(long);
  93.         indistinctwords += file_size (ink[i]) / sizeof(KEY_REC);
  94.       }
  95.     printf ("Merge pass #%d.%d\n", generation_number, file_number / NMERGE);
  96.     printf ("Input files contain %ld words -- %ld distinct words...\n",
  97.                 inwords, indistinctwords);
  98.  
  99.     nway_merge_kpfiles (ink, inp, outk, outp, n);
  100.     
  101.     outdistinctwords = file_size (outk) / sizeof(KEY_REC);
  102.     printf (" ... merged result has %ld distinct words.\n",
  103.                 outdistinctwords);
  104.     
  105.     close_infiles (ink, inp, n);
  106.     fclose (outk);
  107.     fclose (outp);
  108.     remove_used_infiles (generation_number, file_number, n);
  109.     
  110.     file_number += NMERGE;
  111.     
  112.     return (TRUE);
  113.   }
  114.  
  115.